#!/usr/bin/env python

class RBTree(object):
    def __init__(self):
    
        self.nil = self.Node(None)
        self.root = self.nil
        
        
    def LeftRotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.nil:
            y.left.p = x
        y.p = x.p
        if x.p == self.nil:
            self.root = y
        elif x == x.p.left:
            x.p.left = y
        else:
            x.p.right = y
        y.left = x
        x.p = y
        
    def RightRotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != self.nil:
            y.right.p = x
        y.p = x.p
        if x.p == self.nil:
            self.root = y
        elif x == x.p.right:
            x.p.right = y
        else:
            x.p.left = y
        y.right = x
        x.p = y    
        
    def InsertFixup(self, z):
        while z.p.colour == 'r':
            
            if z.p == z.p.p.left:
                try:
                    y = z.p.p.right
                    if y.colour == 'r':
                        z.p.colour = 'b'
                        y.colour = 'b'
                        z.p.p.colour = 'r'
                        z = z.p.p
                    else:
                        if z == z.p.right:
                            z = z.p
                            self.LeftRotate(z)
                        z.p.colour = 'b'
                        z.p.p.colour = 'r'
                        self.RightRotate(z.p.p)
                except:
                    pass
            else:
                try:
                    y = z.p.p.left
                    if y.colour == 'r':
                        z.p.colour = 'b'
                        y.colour = 'b'
                        z.p.p.colour = 'r'
                        z = z.p.p
                    else:
                        if z == z.p.left:
                            z = z.p
                            self.RightRotate(z)
                        z.p.colour = 'b'
                        z.p.p.colour = 'r'
                        self.LeftRotate(z.p.p)
                except:
                    pass
            self.root.colour = 'b'
                
    
    def InsertNode(self, z):
        y = self.nil
        x = self.root
        
        while x != self.nil:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.p = y
        if y == self.nil:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
        z.left = self.nil
        z.right = self.nil
        z.colour = 'r'
        self.InsertFixup(z)
        
    def InsertKey(self, z):
        self.InsertNode(self.Node(z))
    
    def Search(self, key, toSearch=None):
        if toSearch == None:
            toSearch = self.root
        while toSearch != self.nil and key != toSearch.key:
            if key < toSearch.key:
                toSearch = toSearch.left
            else:
                toSearch = toSearch.right
        return toSearch

    
    class Node(object):
        def __init__(self,key=None):
            self.colour = 'b'
            self.left = None
            self.right = None
            self.key = key
            self.p = None
            
        def __str___(self):
            return str(self.key)
        
def write_tree_as_dot(t, f, show_nil=False):
    "Write the tree in the dot language format to f."
    def node_id(node):
        return 'N%d' % id(node)       
            
if '__main__' == __name__:
    import os, sys, random
    def write_tree(t, filename):
        "Write the tree as an SVG file."
        f = open('%s.dot' % filename, 'w')
        write_tree_as_dot(t, f)
        f.close()
        os.system('dot %s.dot -Tsvg -o %s.svg' % (filename, filename))
    '''
    # test the rbtree
    R.seed(2)
    size=50
    keys = R.randint(-50, 50, size=size)
    t = RBTree()
    test_tree(t, keys)
    write_tree(t, 'tree')
    '''
    
    t = RBTree()
    t.InsertKey(5)
    t.InsertKey(15)
    t.InsertKey(25)
    t.InsertKey(14)
    t.InsertKey(52)
    t.InsertKey(64)
    t.InsertKey(3)
    